12
12

Sep 23, 2013
09/13

by
Amitabh Basu; Robert Hildebrand; Matthias Köppe

######
12

######
0

######
0

Recently, cutting planes derived from maximal lattice-free convex sets have been studied intensively by the integer programming community. An important question in this research area has been to decide whether the closures associated with certain families of lattice-free sets are polyhedra. For a long time, the only result known was the celebrated theorem of Cook, Kannan and Schrijver who showed that the split closure is a polyhedron. Although some fairly general results were obtained by...

Source: http://arxiv.org/abs/1111.1780v2

25
25

Jul 20, 2013
07/13

by
Amitabh Basu; Kipp Martin; Chris Ryan

######
25

######
0

######
0

We consider semi-infinite linear programs with countably many constraints indexed by the natural numbers. When the constraint space is the vector space of all real valued sequences, we show the finite support (Haar) dual is equivalent to the algebraic Lagrangian dual of the linear program. This settles a question left open by Anderson and Nash [Linear programming in infinite dimensional spaces : theory and applications, Wiley 1987]. This result implies that if there is a duality gap between the...

Source: http://arxiv.org/abs/1304.3832v1

39
39

Jul 20, 2013
07/13

by
Amitabh Basu; Kipp Martin; Chris Ryan

######
39

######
0

######
0

Fourier-Motzkin elimination is a projection algorithm for solving finite linear programs. We extend Fourier-Motzkin elimination to semi-infinite linear programs which are linear programs with finitely many variables and infinitely many constraints. Applying projection leads to new characterizations of important properties for primal-dual pairs of semi-infinite programs such as zero duality gap, feasibility, boundedness, and solvability. Extending the Fourier-Motzkin elimination procedure to...

Source: http://arxiv.org/abs/1304.3030v1

6
6.0

Sep 22, 2013
09/13

by
Amitabh Basu; Robert Hildebrand; Matthias Koeppe

######
6

######
0

######
0

We give an algorithm for testing the extremality of a large class of minimal valid functions for the two-dimensional infinite group problem.

Source: http://arxiv.org/abs/1210.6732v2

11
11

Sep 21, 2013
09/13

by
Amitabh Basu; Jesus De Loera; Mark Junod

######
11

######
0

######
0

We discuss the method recently proposed by S. Chubanov for the linear feasibility problem. We present new, concise proofs and interpretations of some of his results. We then show how our proofs can be used to find strongly polynomial time algorithms for special classes of linear feasibility problems. Under certain conditions, these results provide new proofs of classical results obtained by Tardos, and Vavasis and Ye.

Source: http://arxiv.org/abs/1204.2031v1

19
19

Jul 20, 2013
07/13

by
Amitabh Basu; Robert Hildebrand; Matthias Köppe

######
19

######
0

######
0

We study a mixed integer linear program with m integer variables and k non-negative continuous variables in the form of the relaxation of the corner polyhedron that was introduced by Andersen, Louveaux, Weismantel and Wolsey [Inequalities from two rows of a simplex tableau, Proc. IPCO 2007, LNCS, vol. 4513, Springer, pp. 1--15]. We describe the facets of this mixed integer linear program via the extreme points of a well-defined polyhedron. We then utilize this description to give polynomial...

Source: http://arxiv.org/abs/1107.5068v1

12
12

Sep 22, 2013
09/13

by
Amitabh Basu; Gérard Cornuéjols; Matthias Köppe

######
12

######
0

######
0

For a minimal inequality derived from a maximal lattice-free simplicial polytope in $\R^n$, we investigate the region where minimal liftings are uniquely defined, and we characterize when this region covers $\R^n$. We then use this characterization to show that a minimal inequality derived from a maximal lattice-free simplex in $\R^n$ with exactly one lattice point in the relative interior of each facet has a unique minimal lifting if and only if all the vertices of the simplex are lattice...

Source: http://arxiv.org/abs/1103.4112v2

7
7.0

Sep 24, 2013
09/13

by
Amitabh Basu; Robert Hildebrand; Matthias Köppe; Marco Molinaro

######
7

######
0

######
0

We prove that any minimal valid function for the k-dimensional infinite group relaxation that is piecewise linear with at most k+1 slopes and does not factor through a linear map with non-trivial kernel is extreme. This generalizes a theorem of Gomory and Johnson for k=1, and Cornuejols and Molinaro for k=2.

Source: http://arxiv.org/abs/1109.4184v1